package uf;

/**
 * 使用数组模拟一下并查集的 quick find
 */
public class QuickFind implements UF{

    // 并查集映射元素的数组
    private int[] id;
    public QuickFind(int size) {
        id = new int[size];
        for (int i = 0; i < id.length; i++)
            id[i] = i;
    }

    private int find(int p) { // find 是O(1)的操作, 所以是 QuickFind
        if (p < 0 || p >= id.length)
            throw new IllegalArgumentException("p is out of bound");
        return id[p]; // 返回p元素所属的集合
    }

    @Override
    public boolean isConnected(int p, int q) { // O(1)
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) { // O(n)
        int pId = find(p);
        int qId = find(p);
        if (pId == qId) return; // 已经是同一个集合中的元素(相连)

        for (int i = 0; i < id.length; i++)
            if (id[i] == pId) id[i] = qId; // 更新到同一个集合中
    }

    @Override
    public int size() { // 并查集中元素的数量
        return id.length;
    }
}
